{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue\n",
    "import numpy as np\n",
    "from scipy import optimize\n",
    "def LP(m, clist, alist, blist, aeqlist, beqlist, all_x=()):\n",
    "    c = np.array(clist)\n",
    "    a = np.array(alist)\n",
    "    b = np.array(blist)\n",
    "    aeq = np.array(aeqlist)\n",
    "    beq = np.array(beqlist)\n",
    "    if m == 'min':\n",
    "        res = optimize.linprog(c, a, b, aeq, beq, bounds=all_x)\n",
    "        fun = res.fun\n",
    "        x = res.x\n",
    "    else:\n",
    "        res = optimize.linprog(-c, a, b, aeq, beq, bounds=all_x)\n",
    "        fun = -res.fun\n",
    "        x = res.x\n",
    "    return fun, x\n",
    "\n",
    "class UFLPsolver:\n",
    "    def __init__(self, n, m, c, f, h=None):\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.c = c\n",
    "        self.f = f\n",
    "        if h:\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    self.f[i][j] *= h[i]\n",
    "\n",
    "    def solve(self, x):\n",
    "        mm = 'min'\n",
    "        clist = list()\n",
    "        for i in range(self.m):\n",
    "            clist.append(self.f[i])\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.m):\n",
    "                clist.append(self.c[i][j])\n",
    "        blist = list()\n",
    "        alist = list()\n",
    "        num = self.m + self.n * self.m\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.m):\n",
    "                tmp = [0] * num\n",
    "                blist.append(0)\n",
    "                tmp[j] = -1\n",
    "                tmp[self.m + self.m * i + j] = 1\n",
    "                alist.append(tmp)\n",
    "        aeqlist = list()\n",
    "        beqlist = list()\n",
    "        for i in range(self.n):\n",
    "            tmp = [0] * num\n",
    "            for j in range(self.m):\n",
    "                tmp[self.m + i * self.m + j] = 1\n",
    "            beqlist.append(1)\n",
    "            aeqlist.append(tmp)\n",
    "        all_x = list()\n",
    "        for i in range(num):\n",
    "            if x[i]:\n",
    "                all_x.append((x[i], x[i]))\n",
    "            else:\n",
    "                all_x.append((0, 1))\n",
    "        value, sol = LP(mm, clist, alist, blist, aeqlist, beqlist, all_x)\n",
    "        return value, sol\n",
    "\n",
    "class BranchBoundSolver:\n",
    "    def __init__(self, n, m, c, f):\n",
    "        self.best_ans = float('inf')\n",
    "        self.best_sol = None\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.c = c\n",
    "        self.f = f\n",
    "        self.solver = UFLPsolver(n, m, c, f)\n",
    "        self.eps = 1e-5\n",
    "\n",
    "    # 广度优先分支定界\n",
    "    def bfs(self, depth, x):\n",
    "        pass\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "    def solvebfs(self):\n",
    "        self.bfs(depth=0, x=[None] * self.m)\n",
    "        print('object value:', format(self.best_ans, '.2f'))\n",
    "        for i in range(len(self.best_sol)):\n",
    "            self.best_sol[i] = format(self.best_sol[i], '.2f')\n",
    "        print('x:', self.best_sol[:self.m])\n",
    "        y = list()\n",
    "        for i in range(self.n):\n",
    "            y.append(self.best_sol[self.m + i * self.m: self.m + (i + 1) * self.m])\n",
    "        print('y:', y)\n",
    "    \n",
    "    #深度优先分支定界\n",
    "    def dfs(self, depth, x):\n",
    "        pass\n",
    "    \n",
    "    def solvedfs(self):\n",
    "        self.dfs(depth=0, x=[None] * self.m)\n",
    "        print('object value:', format(self.best_ans, '.2f'))\n",
    "        for i in range(len(self.best_sol)):\n",
    "            self.best_sol[i] = format(self.best_sol[i], '.2f')\n",
    "        print('x:', self.best_sol[:self.m])\n",
    "        y = list()\n",
    "        for i in range(self.n):\n",
    "            y.append(self.best_sol[self.m + i * self.m: self.m + (i + 1) * self.m])\n",
    "        print('y:', y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 求解\n",
    "# self.solver.solve(x + [None] * self.n * self.m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = [[2, 5, 7], [6, 7, 1], [7, 4, 6], [4, 3, 5]]\n",
    "f = [5, 4, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "INF = float('inf')\n",
    "\n",
    "c = [[120, 210, 180, 210, 170],\n",
    "        [180, INF, 190, 190, 150],\n",
    "        [100, 150, 110, 150, 110],\n",
    "        [INF, 240, 195, 180, 150],\n",
    "        [60, 55, 50, 65, 70],\n",
    "        [INF, 210, INF, 120, 195],\n",
    "        [180, 110, INF, 160, 200],\n",
    "        [INF, 165, 195, 120, INF]]\n",
    "f = [100, 70, 60, 110, 80]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "5179d32cf6ec497baf3f8a3ef987cc77c5d2dc691fdde20a56316522f61a7323"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
